package com.gitee.wsl.collections.trie.analyzer

import com.gitee.wsl.ext.base.Character
import com.gitee.wsl.ext.base.SIZE
import com.gitee.wsl.ext.bitcode.numberOfLeadingZeros
import kotlin.math.max


/**
 * An [KeyAnalyzer] for [String]s.
 *
 *
 * This class is stateless.
 *
 * @since 4.0
 */
class StringKeyAnalyzer() : KeyAnalyzer<String?>() {
    public override fun bitIndex(
        key: String?, offsetInBits: Int, lengthInBits: Int,
        other: String?, otherOffsetInBits: Int, otherLengthInBits: Int,
    ): Int {
        var allNull = true

        require(!(offsetInBits % LENGTH != 0 || otherOffsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0 || otherLengthInBits % LENGTH != 0)) { "The offsets and lengths must be at Character boundaries" }

        val beginIndex1 = offsetInBits / LENGTH
        val beginIndex2 = otherOffsetInBits / LENGTH

        val endIndex1 = beginIndex1 + lengthInBits / LENGTH
        val endIndex2 = beginIndex2 + otherLengthInBits / LENGTH

        val length = max(endIndex1, endIndex2)

        // Look at each character, and if they're different
        // then figure out which bit makes the difference
        // and return it.
        var k = 0.toChar()
        var f = 0.toChar()
        for (i in 0..<length) {
            val index1 = beginIndex1 + i
            val index2 = beginIndex2 + i

            if (index1 >= endIndex1) {
                k = 0.toChar()
            } else {
                 key?.get(index1)?.let { k =it }
            }

            if (other == null || index2 >= endIndex2) {
                f = 0.toChar()
            } else {
                f = other[index2]
            }

            if (k != f) {
                val x = k.code xor f.code
                return i * LENGTH + x.numberOfLeadingZeros() - LENGTH
            }

            if (k.code != 0) {
                allNull = false
            }
        }

        // All bits are 0
        if (allNull) {
            return NULL_BIT_KEY
        }

        // Both keys are equal
        return EQUAL_BIT_KEY
    }

    public override fun bitsPerElement(): Int {
        return LENGTH
    }

    public override fun isBitSet(key: String?, bitIndex: Int, lengthInBits: Int): Boolean {
        if (key == null || bitIndex >= lengthInBits) {
            return false
        }

        val index = bitIndex / LENGTH
        val bit = bitIndex % LENGTH

        return (key[index].code and mask(bit)) != 0
    }

    public override fun isPrefix(
        prefix: String?, offsetInBits: Int,
        lengthInBits: Int, key: String?,
    ): Boolean {
        require(!(offsetInBits % LENGTH != 0 || lengthInBits % LENGTH != 0)) { "Cannot determine prefix outside of Character boundaries" }

        val s1 = prefix?.substring(offsetInBits / LENGTH, lengthInBits / LENGTH)?:return false
        return key?.startsWith(s1) ?: false
    }

    public override fun lengthInBits(key: String?): Int {
        return if (key != null) key.length * LENGTH else 0
    }

    companion object {

        /** A singleton instance of [StringKeyAnalyzer].  */
        val INSTANCE: StringKeyAnalyzer = StringKeyAnalyzer()

        /** The number of bits per [Character].  */
        val LENGTH: Int = Character.SIZE

        /** A bit mask where the first bit is 1 and the others are zero.  */
        private const val MSB = 0x8000

        /** Returns a bit mask where the given bit is set.  */
        private fun mask(bit: Int): Int {
            return MSB ushr bit
        }
    }
}
